"""
例6　下一个更大的数
1．问题描述
两个不重复的数组nums1和nums2，其中nums1是nums2的子集。在
nums2的相应位置找到nums1所有元素的下一个更大数字。
nums1中的数字x的下一个更大数字是nums2中x右边第1个更大的数
字。如果它不存在，则为此数字输出-1。nums1和nums2中的所有数字都
是唯一的，nums1和nums2的长度不超过1000。
2．问题示例
输入nums1=[4，1，2]，nums2=[1，3，4，2]，输出[-1，3，-1]。对
于第1个数组中的数字4，在第2个数组中找不到下一个更大的数字，因
此输出-1；对于第1个数组中的数字1，第2个数组中的下一个更大数字
是3；对于第1个数组中的数字2，第2个数组中没有下一个更大的数字，
因此输出-1
"""


def nextGreaterElement(nums1, nums2):
    # 使用栈来辅助查找下一个更大的数
    stack = []
    # 存储每个数字的下一个更大数字的字典
    next_greater = {}

    # 遍历nums2数组
    for num in nums2:
        # 如果栈不为空且当前数字大于栈顶元素，则找到下一个更大数字
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        # 将当前数字加入栈中
        stack.append(num)

    # 构建输出结果数组
    result = []
    # 遍历nums1数组
    for num in nums1:
        # 根据记录的结果获取下一个更大数字，如果不存在则为-1
        result.append(next_greater.get(num, -1))

    return result


nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
output = nextGreaterElement(nums1, nums2)
print(output)  # 输出 [-1, 3, -1]
